/*
 * @lc app=leetcode.cn id=4 lang=cpp
 *
 * [4] 寻找两个正序数组的中位数
 */

#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        find(nums1, 0, m - 1, nums2, 0, n - 1, m + n / 2);
    }

    double find(vector<int>& nums1, int l1, int h1, vector<int>& nums2, int l2, int h2, int k){
        if(h1 < l1 or h2 < h2){

        }

        int p1 = (l1 + h1) / 2;
        int p2 = (l2 + h2) / 2;
        if (nums1[p1] > nums2[p2]){
            if (k < p1 + p2 + 1){
                find(nums1, l1, p1 - 1, nums2, l2, h2, k);
            }
            else if (k >= p1 + p2 + 1)
            {
                find(nums1, l1, p1, nums2, p2 + 1, h2, k);
            }
            
        }
        else if(nums1[p1] < nums2[p2]) {
            if (k < p1 + p2 + 1){
                find(nums2, l2, p2 - 1, nums1, l1, h1, k);
            }
            else if (k >= p1 + p2 + 1)
            {
                find(nums2, l2, p2, nums1, p1 + 1, h1, k);
            }
        }
        else{
            if (k < p1 + p2){
                find(nums1, l1, p1 - 1, nums2, l2, p2 - 1, k);
            }
            else if (k > p1 + p2 + 1)
            {
                find(nums1, p1 + 1, l1, nums2, p2 + 1, l2, k);
            }
            else{
                
                return p1 + (p1 + p2 - k);
            }
            
        }
    }
};
// @lc code=end

